package com.sise.Linked;

import java.util.HashMap;
import java.util.Map;

/**
 *      剑指 Offer 35. 复杂链表的复制
 *
 *      请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 */
public class _offer_35_copyRandomList {

    /**
     *      根据原链表先复制一份，然后构建 random 指向，最终拆分链表
     */
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node cur = head;

        // 1、赋值各节点，并构建拼接链表
        while (cur != null){
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;             // 拼接完成

            cur = tmp.next;             // 移动到第三个位置
        }

        // 2、构建各新节点的 random 指向
        cur = head;
        while (cur != null){
            if (cur.random != null){
                cur.next.random = cur.random.next;      // 因为上一步已经复制了一份，故此这里引用它的下一个元素
            }
            cur = cur.next.next;
        }

        // 3、拆分两链表
        cur = head.next;
        Node pre = head;
        Node res = head.next;
        while (cur.next != null){
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null;                // 单独处理原链表的尾结点
        return res;
    }


    /**
     *      通过建立 Map 映射，第一遍遍历先赋值，遍历完成后，将 cur 重新置为 head，然后再次遍历赋 next，random
     */
    public Node copyRandomList_2(Node head) {
        if (head == null) return null;

        Map<Node, Node> map = new HashMap<>();

        // 第一次赋值
        Node cur = head;
        while (cur != null){
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        // 第二次赋 next、random
        cur = head;
        while (cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }
}
